package com.wyr.leetcode.step3;

/**
 * 给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
 *
 * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
 *
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * 给定 n 和 k，返回第 k 个排列。
 *
 * https://leetcode.cn/problems/permutation-sequence/description/
 */
public class GetPermutation {

    public static void main(String[] args) {
        getPermutation(3,4);
    }

    static int [] jieChen;
    public static String getPermutation(int n, int k) {
        // 计算阶乘法
        // 1！=1 1个数的全排列结果为1
        // 2！=2 2个数的全排列结果为2
        // 3！=6 3个数的全排列结果为6
        // 4！=24 4个数的全排列结果为24
        computeJieChen(n);
        int [] used = new int[n];
        StringBuilder sb = new StringBuilder();
        dfs(0, n, used, k, sb);
        return sb.toString();
    }
    // fixCount：已经固定了几个数，n：一共需要固定的数的个数
    // k：目标字符串，未固定数的全排列中排第几位
    public static void dfs(int fixCount, int n, int []used, int k, StringBuilder path){
        if(fixCount == n){
            return;
        }
        for(int i=1;i<=n;i++){
            // 当前数已使用,跳过
            if(used[i-1]==1){
                continue;
            }
            // 假设使用当前数，进入下一层
            // 假设情况下，未固定的数的全排列个数
            int lastCount = jieChen[n-1-fixCount];
            if(k>lastCount){
                k-=lastCount;
                continue;
            }
            used[i-1] = 1;
            // 选择当前数i进行固定
            dfs(fixCount+1,n,used,k,path.append(i));
        }
    }


    public static void computeJieChen(int n) {
        jieChen = new int[n + 1];
        jieChen[0] = 1;
        for (int i = 1; i <= n; i++) {
            jieChen[i] = jieChen[i - 1] * i;
        }
    }
}
